﻿// <copyright file="MaxListAccumulator.cs" company="Ecole Normale Supérieure">
// Released under GPLv2
// </copyright>
// <summary>Contains the MaxListAccumulator.</summary>

namespace Sqwarea.GameLogic.TopList
{
    using System.Collections.Generic;
    using System.Linq;

    /// <summary>
    /// A quick-written constant time top list extractor. We assume that key > 0.
    /// </summary>
    /// <typeparam name="T">The type that stores data.</typeparam>
    public class MaxListAccumulator<T>
    {
        /// <summary>
        /// An ascending sorted array containing all keys.
        /// </summary>
        private int[] _keys = new int[GlobalParameters.TopListLength];

        /// <summary>
        /// An array containing data corresponding to the array _keys
        /// </summary>
        private T[] _data = new T[GlobalParameters.TopListLength];

        /// <summary>
        /// An object of type T meaning that the data is null
        /// </summary>
        private T _emptyData;

        /// <summary>
        /// Initializes a new instance of the MaxListAccumulator class
        /// </summary>
        /// <param name="emptyData">An object of type T that is considered to be nothing</param>
        public MaxListAccumulator(T emptyData)
        {
            _emptyData = emptyData;
            for (int i = 0; i < GlobalParameters.TopListLength; i++)
            {
                _keys[i] = -1;
                _data[i] = emptyData;
            }
        }

        /// <summary>
        /// Try to add a key/data pair into this MaxListAccumulator
        /// </summary>
        /// <param name="key">The key used to compare</param>
        /// <param name="data">The data with this key</param>
        public void Add(int key, T data)
        {
            if (key > _keys[0])
            {
                int i = 0;
                while ((i < GlobalParameters.TopListLength - 1) && (key > _keys[i + 1]))
                {
                    _keys[i] = _keys[i + 1];
                    _data[i] = _data[i + 1];
                    i++;
                }
                //// As GlobalParameters.TopListLength is small, insertion sort is fast enough.

                _keys[i] = key;
                _data[i] = data;
            }
        }

        /// <summary>
        /// Return the list of data, sorted with key descending
        /// </summary>
        /// <returns>The list of data to return</returns>
        public IEnumerable<T> MaxList()
        {
            var list = from d in _data
                       where !d.Equals(_emptyData)
                       select d;
            return list.Reverse();
        }
    }
}
